package com.yanceysong.codetop.s91_s100;

public class S94_Mid_209_长度最小的子数组 {
    /**
     * .S94_Mid_209_长度最小的子数组
     * .<p>
     * .<a href="https://leetcode.cn/problems/minimum-size-subarray-sum/">...</a>
     * .<p>
     * .给定一个含有 n 个正整数的数组和一个正整数 target 。
     * .<p>
     * .找出该数组中满足其总和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，
     * .并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * .<p>
     * .示例：
     * .<p>
     * .输入：target = 7, nums = [2,3,1,2,4,3]
     * .输出：2
     * .解释：子数组 [4,3] 是该条件下的长度最小的子数组。
     * .<p>
     * .输入：target = 4, nums = [1,4,4]
     * .输出：1
     * .<p>
     * .输入：target = 11, nums = [1,1,1,1,1,1,1,1]
     * .输出：0
     * .<p>
     * .提示：
     * .<p>
     * .1 <= target <= 10^9
     * .1 <= nums.length <= 10^5
     * .1 <= nums[i] <= 10^5
     * .<p>
     * .核心标签：数组、滑动窗口、双指针、前缀和
     * .<p>
     * .算法原理：滑动窗口（双指针）
     * .- 使用两个指针 left 和 right 维护一个滑动窗口
     * .- right 指针不断向右扩展窗口，将元素加入窗口
     * .- 当窗口内元素和 >= target 时，尝试收缩窗口（移动 left 指针）
     * .- 在满足条件的情况下，记录最小窗口长度
     * .- 继续移动 right 指针，重复上述过程
     * .<p>
     * .关键洞察：
     * .1. 由于数组元素都是正整数，窗口和具有单调性
     * .2. 当窗口和 >= target 时，继续扩大窗口只会让和更大，不会得到更优解
     * .3. 因此需要收缩窗口（移动左指针），寻找更小的满足条件的窗口
     * .4. 这是一个典型的滑动窗口问题，时间复杂度可以优化到 O(n)
     * .<p>
     * .图解示例：target = 7, nums = [2,3,1,2,4,3]
     * .<p>
     * .初始状态：
     * .[2, 3, 1, 2, 4, 3]
     * .L
     * .R
     * .sum = 0, minLen = ∞
     * .<p>
     * .步骤1：R右移，sum = 2 < 7，继续扩展
     * .[2, 3, 1, 2, 4, 3]
     * .L  R
     * .sum = 2
     * .<p>
     * .步骤2：R右移，sum = 5 < 7，继续扩展
     * .[2, 3, 1, 2, 4, 3]
     * .L     R
     * .sum = 5
     * .<p>
     * .步骤3：R右移，sum = 6 < 7，继续扩展
     * .[2, 3, 1, 2, 4, 3]
     * .L        R
     * .sum = 6
     * .<p>
     * .步骤4：R右移，sum = 8 >= 7，满足条件！
     * .[2, 3, 1, 2, 4, 3]
     * .L           R
     * .sum = 8, minLen = 4 (当前窗口长度)
     * .<p>
     * .步骤5：尝试收缩窗口，L右移，sum = 6 < 7，不满足
     * .[2, 3, 1, 2, 4, 3]
     * .L        R
     * .sum = 6
     * .<p>
     * .步骤6：R右移，sum = 10 >= 7，满足条件！
     * .[2, 3, 1, 2, 4, 3]
     * .L              R
     * .sum = 10, minLen = 4
     * .<p>
     * .步骤7：尝试收缩窗口，L右移，sum = 8 >= 7，仍满足！
     * .[2, 3, 1, 2, 4, 3]
     * .L           R
     * .sum = 8, minLen = 3
     * .<p>
     * .步骤8：继续收缩，L右移，sum = 7 >= 7，仍满足！
     * .[2, 3, 1, 2, 4, 3]
     * .L        R
     * .sum = 7, minLen = 2
     * .<p>
     * .步骤9：继续收缩，L右移，sum = 4 < 7，不满足
     * .[2, 3, 1, 2, 4, 3]
     * .L     R
     * .sum = 4
     * .<p>
     * .步骤10：R右移，sum = 7 >= 7，满足条件！
     * .[2, 3, 1, 2, 4, 3]
     * .L           R
     * .sum = 7, minLen = 2
     * .<p>
     * .步骤11：继续收缩，L右移，sum = 3 < 7，不满足
     * .[2, 3, 1, 2, 4, 3]
     * .L        R
     * .sum = 3
     * .<p>
     * .R已到达数组末尾，结束。最小长度 = 2
     * .<p>
     * .滑动窗口的核心思想：
     * .┌─────────────────────────────────┐
     * .│  扩展窗口（右指针右移）          │
     * .│         ↓                       │
     * .│  [  L -------- R  ]             │
     * .│         ↑                       │
     * .│  收缩窗口（左指针右移）          │
     * .└─────────────────────────────────┘
     * .<p>
     * .时间复杂度：O(n)，其中 n 为数组长度
     * .- 虽然有两层循环，但每个元素最多被访问两次（一次被右指针访问，一次被左指针访问）
     * .- 左指针和右指针都只会向右移动，不会回退
     * .<p>
     * .空间复杂度：O(1)，只使用了常数个变量
     */
    public int minSubArrayLen(int target, int[] nums) {
        int arrayLength = nums.length;
        
        // 边界条件检查：空数组
        if (arrayLength == 0) {
            return 0;
        }

        // 初始化最小长度为最大值（表示还未找到满足条件的子数组）
        int minLength = Integer.MAX_VALUE;
        
        // 滑动窗口的左右边界
        int leftPointer = 0;
        int rightPointer = 0;
        
        // 当前窗口内元素的和
        int windowSum = 0;

        // 右指针向右移动，扩展窗口
        while (rightPointer < arrayLength) {
            // 将右指针指向的元素加入窗口
            windowSum += nums[rightPointer];

            // 当窗口内元素和 >= target 时，尝试收缩窗口
            while (windowSum >= target) {
                // 更新最小长度
                minLength = Math.min(minLength, rightPointer - leftPointer + 1);
                
                // 将左指针指向的元素移出窗口
                windowSum -= nums[leftPointer];
                
                // 左指针右移，收缩窗口
                leftPointer++;
            }

            // 右指针右移，继续扩展窗口
            rightPointer++;
        }

        // 如果 minLength 仍为初始值，说明没有找到满足条件的子数组，返回 0
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        S94_Mid_209_长度最小的子数组 solution = new S94_Mid_209_长度最小的子数组();

        System.out.println("=== 长度最小的子数组测试开始 ===");

        // 测试1: 题目示例1 - target = 7, nums = [2,3,1,2,4,3]
        System.out.println("\n--- 测试1: target = 7, nums = [2,3,1,2,4,3] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - target = 4, nums = [1,4,4]
        System.out.println("\n--- 测试2: target = 4, nums = [1,4,4] ---");
        testCase2(solution);

        // 测试3: 题目示例3 - target = 11, nums = [1,1,1,1,1,1,1,1]
        System.out.println("\n--- 测试3: target = 11, nums = [1,1,1,1,1,1,1,1] ---");
        testCase3(solution);

        // 测试4: 空数组
        System.out.println("\n--- 测试4: 空数组 ---");
        testEmptyArray(solution);

        // 测试5: 单元素数组，满足条件
        System.out.println("\n--- 测试5: 单元素数组，满足条件 ---");
        testSingleElementSatisfied(solution);

        // 测试6: 单元素数组，不满足条件
        System.out.println("\n--- 测试6: 单元素数组，不满足条件 ---");
        testSingleElementNotSatisfied(solution);

        // 测试7: 整个数组和刚好等于target
        System.out.println("\n--- 测试7: 整个数组和等于target ---");
        testWholeArraySum(solution);

        // 测试8: 第一个元素就满足条件
        System.out.println("\n--- 测试8: 第一个元素就满足条件 ---");
        testFirstElementSatisfied(solution);

        // 测试9: 最后一个元素满足条件
        System.out.println("\n--- 测试9: 最后一个元素满足条件 ---");
        testLastElementSatisfied(solution);

        // 测试10: 连续相同元素
        System.out.println("\n--- 测试10: 连续相同元素 ---");
        testConsecutiveSameElements(solution);

        // 测试11: 大数组测试
        System.out.println("\n--- 测试11: 大数组测试 ---");
        testLargeArray(solution);

        // 测试12: target很大，无解
        System.out.println("\n--- 测试12: target很大，无解 ---");
        testNoSolution(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: target = 7, nums = [2,3,1,2,4,3]
     * .期望输出：2（子数组 [4,3]）
     */
    private static void testCase1(S94_Mid_209_长度最小的子数组 solution) {
        int target = 7;
        int[] nums = {2, 3, 1, 2, 4, 3};

        System.out.println("输入: target = " + target + ", nums = [2,3,1,2,4,3]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 2)");
        System.out.println("解释: 子数组 [4,3] 的和为 7，长度为 2");

        assert result == 2 : "测试1失败：期望2，实际" + result;
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: target = 4, nums = [1,4,4]
     * .期望输出：1（子数组 [4]）
     */
    private static void testCase2(S94_Mid_209_长度最小的子数组 solution) {
        int target = 4;
        int[] nums = {1, 4, 4};

        System.out.println("输入: target = " + target + ", nums = [1,4,4]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 1)");
        System.out.println("解释: 子数组 [4] 的和为 4，长度为 1");

        assert result == 1 : "测试2失败：期望1，实际" + result;
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: target = 11, nums = [1,1,1,1,1,1,1,1]
     * .期望输出：0（不存在满足条件的子数组）
     */
    private static void testCase3(S94_Mid_209_长度最小的子数组 solution) {
        int target = 11;
        int[] nums = {1, 1, 1, 1, 1, 1, 1, 1};

        System.out.println("输入: target = " + target + ", nums = [1,1,1,1,1,1,1,1]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 0)");
        System.out.println("解释: 数组总和为 8，小于 target 11，不存在满足条件的子数组");

        assert result == 0 : "测试3失败：期望0，实际" + result;
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 空数组
     * .期望输出：0
     */
    private static void testEmptyArray(S94_Mid_209_长度最小的子数组 solution) {
        int target = 5;
        int[] nums = {};

        System.out.println("输入: target = " + target + ", nums = []");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 0)");

        assert result == 0 : "测试4失败：期望0，实际" + result;
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单元素数组，满足条件
     * .期望输出：1
     */
    private static void testSingleElementSatisfied(S94_Mid_209_长度最小的子数组 solution) {
        int target = 5;
        int[] nums = {10};

        System.out.println("输入: target = " + target + ", nums = [10]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 1)");
        System.out.println("解释: 单个元素 10 >= 5，满足条件");

        assert result == 1 : "测试5失败：期望1，实际" + result;
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 单元素数组，不满足条件
     * .期望输出：0
     */
    private static void testSingleElementNotSatisfied(S94_Mid_209_长度最小的子数组 solution) {
        int target = 10;
        int[] nums = {5};

        System.out.println("输入: target = " + target + ", nums = [5]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 0)");
        System.out.println("解释: 单个元素 5 < 10，不满足条件");

        assert result == 0 : "测试6失败：期望0，实际" + result;
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 整个数组和刚好等于target
     * .期望输出：数组长度
     */
    private static void testWholeArraySum(S94_Mid_209_长度最小的子数组 solution) {
        int target = 15;
        int[] nums = {1, 2, 3, 4, 5};

        System.out.println("输入: target = " + target + ", nums = [1,2,3,4,5]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 5)");
        System.out.println("解释: 整个数组和为 15，等于 target");

        assert result == 5 : "测试7失败：期望5，实际" + result;
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 第一个元素就满足条件
     * .期望输出：1
     */
    private static void testFirstElementSatisfied(S94_Mid_209_长度最小的子数组 solution) {
        int target = 5;
        int[] nums = {10, 1, 2, 3};

        System.out.println("输入: target = " + target + ", nums = [10,1,2,3]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 1)");
        System.out.println("解释: 第一个元素 10 >= 5，满足条件");

        assert result == 1 : "测试8失败：期望1，实际" + result;
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 最后一个元素满足条件
     * .期望输出：1
     */
    private static void testLastElementSatisfied(S94_Mid_209_长度最小的子数组 solution) {
        int target = 10;
        int[] nums = {1, 2, 3, 15};

        System.out.println("输入: target = " + target + ", nums = [1,2,3,15]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 1)");
        System.out.println("解释: 最后一个元素 15 >= 10，满足条件");

        assert result == 1 : "测试9失败：期望1，实际" + result;
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 连续相同元素
     * .期望输出：3
     */
    private static void testConsecutiveSameElements(S94_Mid_209_长度最小的子数组 solution) {
        int target = 15;
        int[] nums = {5, 5, 5, 5, 5};

        System.out.println("输入: target = " + target + ", nums = [5,5,5,5,5]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 3)");
        System.out.println("解释: 需要 3 个 5 才能达到 15");

        assert result == 3 : "测试10失败：期望3，实际" + result;
        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 大数组测试
     * .期望输出：合理的结果
     */
    private static void testLargeArray(S94_Mid_209_长度最小的子数组 solution) {
        int target = 100;
        int[] nums = new int[1000];
        
        // 填充数组：前500个元素为1，后500个元素为2
        for (int i = 0; i < 500; i++) {
            nums[i] = 1;
        }
        for (int i = 500; i < 1000; i++) {
            nums[i] = 2;
        }

        System.out.println("输入: target = " + target + ", nums = [1,1,...(500个1),2,2,...(500个2)]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 50)");
        System.out.println("解释: 需要 50 个 2 才能达到 100");

        assert result == 50 : "测试11失败：期望50，实际" + result;
        System.out.println("✓ 测试11通过");
    }

    /**
     * .测试12: target很大，无解
     * .期望输出：0
     */
    private static void testNoSolution(S94_Mid_209_长度最小的子数组 solution) {
        int target = 1000;
        int[] nums = {1, 2, 3, 4, 5};

        System.out.println("输入: target = " + target + ", nums = [1,2,3,4,5]");
        int result = solution.minSubArrayLen(target, nums);
        System.out.println("输出: " + result + " (期望: 0)");
        System.out.println("解释: 数组总和为 15，远小于 target 1000");

        assert result == 0 : "测试12失败：期望0，实际" + result;
        System.out.println("✓ 测试12通过");
    }
}

